package 不相交的线;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/18 12:35
 * @description:
 * 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
 * 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
 * nums1[i] == nums2[j]
 * 且绘制的直线不与任何其他连线（非水平线）相交。
 * 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
 * 以这种方法绘制线条，并返回可以绘制的最大连线数。
 */
public class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 就是求最长的公共子序列
        // ① dp数组及其下标含义：dp[i][j]表示nums1中以 i-1 结尾的子序列，nums2中以 j-1 结尾的子序列，的最长公共子序列长度
        // ② 状态转移方程：if(nums[i-1] == nums[j-1])  dp[i][j] = dp[i-1][j-1] + 1
        //                  else dp[i][j] = Math.max(dp[i-1][j], d[[i][j-1]);  当不相等的时候，可以选择nums1的或者nums2的
        //                  但是没必须两个都不选，因为选了的始终是最优的 ==> dp[i-1][j-1] <= dp[i][j-1] / dp[i-1][j]
        // ③ dp数组的初始化；我们采取的是 i-1 结尾和 j-1 结尾，所以dp数组初始化为0即可
        // ④ 遍历顺序：从左上角到右下角
        // ⑤ 举例推导dp数组： 输入：nums1 = [1,4,2], nums2 = [1,2,4]
        //          index:     0    1   2   3
        //             0       0    0   0   0
        //             1       0    1   1   1
        //             2       0    1   1   2
        //             3       0    1   2   2

        // 滑动dp数组
        int[] dp = new int[nums2.length + 1];
        int result = 0;
        // 遍历 nums1
        for (int i = 1; i <= nums1.length; i++) {
            // 遍历 nums2
            int pre = 0; // 记录 dp[i-1][j-1]
            for (int j = 1; j <= nums2.length; j++) {
                int cur = dp[j];
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = pre + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                pre = cur;
                result = Math.max(result, dp[j]);
            }
            System.out.println(Arrays.toString(dp));
        }

        return result;
    }
}
